#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 *  https://www.bilibili.com/video/BV1MK411j7CR/?vd_source=414fd381c40fd85cbec992fd7202bf29
 *
 */

#define leaf_node_num 8                        // 叶子结点数
#define node_total_num (2 * leaf_node_num - 1) // 哈夫曼树中的结点总数

// --------------------哈夫曼树--------------------
// 定义哈夫曼结点的存储结构
typedef struct htnode
{
    char name;    // 定义该结点的名字
    int lchild;   // 左孩子
    int rchild;   // 左孩子
    int weight; // 权值
    int parent;   // 双亲指针
} HTNode;         // 树中结点类型

typedef HTNode *HuffmanTree;

void findTowMinValue(HuffmanTree HT, int n, int *min, int *submin)
{
    for (int i = 0; i < n; i++)
    {
        // HT[i]
        *min = 1;
        *submin = 2;
    }
}

/**
 * 创建哈夫曼树， n 为结点数， names 为n个结点的名称， weights 为结点对应的权值
 */
HuffmanTree createHuffmanTree(int n, char names[n], int weights[n])
{
    // 总结点数
    int totalnodenum = 2 * n - 1;
    // 申请所有结点空间
    HuffmanTree tree = (HuffmanTree)malloc(totalnodenum * sizeof(HTNode));
    // 初始化所有结点信息，并只初始化前n个结点权值
    for (int i = 0; i < totalnodenum; i++)
    {
        tree[i].lchild = -1;
        tree[i].rchild = -1;
        tree[i].parent = -1;
        // 初始化前 n 个结点的权值及名称
        if (i < n)
        {
            tree[i].name = names[i];
            tree[i].weight = weights[i];
        }
    }

    int mi = -1;  // 最小值的索引
    int smi = -1; // 次小值的索引

    // 构建哈夫曼树. 从n个结点开始
    for (int k = n; k < totalnodenum; k++)
    {
        // 每次找 parent=-1 且 权值最小的两个值(最小值、次小值)
        // TODO: 后续实现下
        findTowMinValue(tree, n, &mi, &smi);
        // 取出两值的权值
        tree[k].weight = tree[mi].weight + tree[smi].weight;
        tree[k].name = tree[k].weight;
        // 关联相关的结点
        tree[k].lchild = mi;
        tree[k].rchild = smi;
        // 更新两最小值结点的父结点
        tree[mi].parent = k;
        tree[smi].parent = k;
    }

    return tree;
}

void printTree(HuffmanTree HT, int n)
{
    for (int i = 0; i < (2*n -1); i++)
    {
        HTNode node = HT[i];
        printf("第%2d个结点: name=%c  weight=%2d  parent=%2d  leftchild=%2d  rightchild=%2d\n", i, node.name,
               node.weight, node.parent, node.lchild, node.rchild);
    }
}

int main()
{
    int c = (2-1)/2;

    printf("===>%d\n", c);
    int n = 4;
    char names[] = {'A', 'B', 'C', 'D', '\0'};
    int weights[] = {2, 3, 4, 5};
    HuffmanTree trees = createHuffmanTree(n, names, weights);
    printTree(trees, 4);
    printf("\n");
    return 0;
}